﻿using System;

namespace AlgorithmPractice;

/// <summary>
/// 快速排序
/// </summary>
public class Quicksort
{
    public static void Sort(int[] toBeSorted)
    {
        RecursionSort(toBeSorted, 0, toBeSorted.Length - 1);
        Console.WriteLine(string.Join("、", toBeSorted));
    }

    /// <summary>
    /// (1) 从数列中挑出一个基准值。
    /// (2) 将所有比基准值小的摆放在基准前面，所有比基准值大的摆在基准的后面(相同的数可以到任一边)；在这个分区退出之后，该基准就处于数列的中间位置。
    /// (3) 递归地把"基准值前面的子数列"和"基准值后面的子数列"进行排序。
    /// </summary>
    /// <param name="toBeSorted"></param>
    /// <param name="low"></param>
    /// <param name="high"></param>
    private static void RecursionSort(int[] toBeSorted, int low, int high)
    {
        if (low < high)
        {
            var firstSortedIndex = StartSort(toBeSorted, low, high);

            RecursionSort(toBeSorted, low, firstSortedIndex - 1);
            RecursionSort(toBeSorted, firstSortedIndex + 1, high);
        }
    }

    private static int StartSort(int[] toBeSorted, int low, int high)
    {
        var temp = toBeSorted[low];

        while (low < high)
        {
            while (toBeSorted[high] >= temp && low < high)
                high--;
            toBeSorted[low] = toBeSorted[high];

            while (toBeSorted[low] <= temp && low < high)
                low++;
            toBeSorted[high] = toBeSorted[low];
        }

        toBeSorted[low] = temp;

        return low;
    }
}